package com.shm.leetcode;
/**
 * @author: shm
 * @dateTime: 2020/9/22 11:19
 * @description: 剑指 Offer 15. 二进制中1的个数
 * 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
 *
 * 示例 1：
 *
 * 输入：00000000000000000000000000001011
 * 输出：3
 * 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
 * 示例 2：
 *
 * 输入：00000000000000000000000010000000
 * 输出：1
 * 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
 * 示例 3：
 *
 * 输入：11111111111111111111111111111101
 * 输出：31
 * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
 *
 *
 * 注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/
 */
public class HammingWeight {

    /**
     * @author: shm
     * @dateTime: 2020/9/22 11:35
     * @description: 方法二：巧用 n \& (n - 1)n&(n−1)
     * (n - 1)(n−1) 解析： 二进制数字 nn 最右边的 11 变成 00 ，此 11 右边的 00 都变成 11 。
     * n \& (n - 1)n&(n−1) 解析： 二进制数字 nn 最右边的 11 变成 00 ，其余不变。
     * 算法流程：
     * 初始化数量统计变量 resres 。
     * 循环消去最右边的 11 ：当 n = 0n=0 时跳出。
     * res += 1 ： 统计变量加 11 ；
     * n &= n - 1 ： 消去数字 nn 最右边的 11 。
     * 返回统计数量 resres 。
     * 复杂度分析：
     * 时间复杂度 O(M)O(M) ： n \& (n - 1)n&(n−1) 操作仅有减法和与运算，占用 O(1)O(1) ；设 MM 为二进制数字 nn 中 11 的个数，则需循环 MM 次（每轮消去一个 11 ），占用 O(M)O(M) 。
     * 空间复杂度 O(1)O(1) ： 变量 resres 使用常数大小额外空间。
     * 方法二：位运算优化
     * 思路及解法
     *
     * 观察这个运算：n~\&~(n - 1)n & (n−1)，其预算结果恰为把 nn 的二进制位中的最低位的 11 变为 00 之后的结果。
     *
     * 如：6~\&~(6-1) = 4, 6 = (110)_2, 4 = (100)_26 & (6−1)=4,6=(110)
     * 2
     * ​
     *  ,4=(100)
     * 2
     * ​
     *  ，运算结果 44 即为把 66 的二进制位中的最低位的 11 变为 00 之后的结果。
     *
     * 这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的 nn 与 n - 1n−1 做与运算，直到 nn 变为 00 即可。因为每次运算会使得 nn 的最低位的 11 被翻转，因此运算次数就等于 nn 的二进制位中 11 的个数。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode-solution-jnwf/
     *
     *
     * 作者：jyd
     * 链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun/
     */
    public int hammingWeight(int n) {
        int res = 0;
        while (n!=0){
            res++;
            n&=n-1;
        }
        return res;
    }

    /**
     * @author: shm
     * @dateTime: 2020/9/22 11:29
     * @description: 方法一：逐位判断
     * 根据 与运算 定义，设二进制数字 nn ，则有：
     * 若 n \& 1 = 0n&1=0 ，则 nn 二进制 最右一位 为 00 ；
     * 若 n \& 1 = 1n&1=1 ，则 nn 二进制 最右一位 为 11 。
     * 根据以上特点，考虑以下 循环判断 ：
     * 判断 nn 最右一位是否为 11 ，根据结果计数。
     * 将 nn 右移一位（本题要求把数字 nn 看作无符号数，因此使用 无符号右移 操作）。
     * 算法流程：
     * 初始化数量统计变量 res = 0res=0 。
     * 循环逐位判断： 当 n = 0n=0 时跳出。
     * res += n & 1 ： 若 n \& 1 = 1n&1=1 ，则统计数 resres 加一。
     * n >>= 1 ： 将二进制数字 nn 无符号右移一位（ Java 中无符号右移为 ">>>>>>" ） 。
     * 返回统计数量 resres 。
     * 复杂度分析：
     * 时间复杂度 O(log_2 n)O(log
     * 2
     * ​
     *  n) ： 此算法循环内部仅有 移位、与、加 等基本运算，占用 O(1)O(1) ；逐位判断需循环 log_2 nlog
     * 2
     * ​
     *  n 次，其中 log_2 nlog
     * 2
     * ​
     *  n 代表数字 nn 最高位 11 的所在位数（例如 log_2 4 = 2log
     * 2
     * ​
     *  4=2, log_2 16 = 4log
     * 2
     * ​
     *  16=4）。
     * 空间复杂度 O(1)O(1) ： 变量 resres 使用常数大小额外空间。
     *
     * 作者：jyd
     * 链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun/
     */
    public int hammingWeight_2(int n) {
        int res = 0;
        while (n!=0){
//            if (n & 1== 1) {
            if ((n & 1) == 1) {
                res++;
            }
            //超时 对于负数，最高位为 1 ，有符号右移 最高位填1，因此无法达到 n = 0，就无法跳出循环了
//            n>>=1;
            n>>>=1;
        }
        return res;
    }

    public int hammingWeight_3(int n) {
//        return Integer.toBinaryString(n).replaceAll("0", "").length();
        return Integer.bitCount(n);
    }


    /**
     * 方法一：循环检查二进制位
     * 思路及解法
     *
     * 我们可以直接循环检查给定整数 nn 的二进制位的每一位是否为 11。
     *
     * 具体代码中，当检查第 ii 位时，我们可以让 nn 与 2^i2
     * i
     *   进行与运算，当且仅当 nn 的第 ii 位为 11 时，运算结果不为 00。
     *   复杂度分析
     *
     * 时间复杂度：O(k)O(k)，其中 kk 是 \texttt{int}int 型的二进制位数，k=32k=32。我们需要检查 nn 的二进制位的每一位，一共需要检查 3232 位。
     *
     * 空间复杂度：O(1)O(1)，我们只需要常数的空间保存若干变量。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode-solution-jnwf/
     * @param n
     * @return
     */
    public int hammingWeight_4(int n) {
        int ans =0;
        for (int i = 0; i < 32; i++) {
            if((n&(1<<i))!=0){
                ans++;
            }
        }
        return ans;
    }
}
